/*
 * @lc app=leetcode.cn id=34 lang=cpp
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
#include <vector>
using namespace std;
class Solution
{
 public:
  // acwing
  vector<int> searchRange(vector<int>& nums, int target)
  {
    if (nums.empty()) return {-1, -1};
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (1 + l + r) >> 1;
      if (nums[mid] <= target)
        l = mid;
      else
        r = mid - 1;
    }

    // 如果连第一个点都没找到，那说明此数组没有target,不用进行第二个元素的查找了，直接返回
    if (nums[l]!=target]) return {-1, -1};
    // 相等存起来
    int last = l;

    l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (l + r) >> 1;
      if (nums[mid] < target)
        l = mid + 1;
      else
        r = mid;
    }

    // 存第二个点
    int start = l;

    return {start, last};
  }
  /* 自己写的
  vector<int> searchRange(vector<int>& nums, int target)
  {
    if (nums.empty()) return {-1, -1};
    int a, b;
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (1 + l + r) >> 1;
      if (nums[mid] <= target)
        l = mid;
      else
        r = mid - 1;
    }
    if (nums[l] == target)
      b = l;
    else
      b = -1;

    l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (l + r) >> 1;
      if (nums[mid] < target)
        l = mid + 1;
      else
        r = mid;
    }
    if (nums[l] == target)
      a = l;
    else
      a = -1;

    vector<int> result;
    result.push_back(a);
    result.push_back(b);

    return result;
  }
  */
};
// @lc code=end
